In traditional data communication networks, routing is primarily concerned with connectivity. To achieve efficient utilization of network resources, the cheapest routes are usually selected by finding the shortest paths using algorithms such as Dijkstra's.
Dijkstra's algorithm, which was developed by Edsger Dijkstra in 1959, is a well known method described in, for example, C. Papadimitriou, K. Steiglitz, (1982), Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, the contents of which are incorporated herein by reference. Dijkstra's algorithm takes a graph with weighted links and a given root vertex as its input and returns, as its output, a label for each vertex on the graph. In the case where the weights represent the length of the links, each vertex label represents the length of the shortest path from the root vertex to the particular vertex. Thus the algorithm allows finding the shortest path for travelling from a given vertex on a graph to every other vertex.
With the arrival of multimedia applications such as video and audio, it is realized that connectivity alone is far from adequate for such applications to be successful. Unlike traditional data communication applications such as e-mail and remote file transfers, live video and audio cannot tolerate excessive delay and need guaranteed maximum delay and bandwidth. To deliver such Quality of Service (QoS) guarantees, a network must make resource reservations and exercise network control. In "Private Network-Network Interface Specification Version 1.0 (PNNI 1.0)," ATM Forum, 1996, resource reservation has been incorporated in the PNNI protocol for Asynchronous Transfer Mode (ATM) communication. As well, "RSVP" has been developed as a resource reservation protocol for the Internet. Multiple QoS metrics such as cost, delay, delay variation, loss probability and bandwidth are accommodated by the PNNI protocol. As a result, the routing problem, that of achieving efficient utilization of network resources, is further complicated by these QoS metrics. The route selection problem is now to find a path from the source to the destination that satisfies all QoS constraints and has the lowest cost.
The most studied QoS metrics fall into two categories. The first category is concave, in which the aggregate metric over a path is the minimum of the values of this metric for all sections of the path. The second category is additive, in which the aggregate metric over a path is the sum of the values of this metric for all sections of the path.
Zheng Wang and Jon Crowcroft, "Quality of Service Routing for Supporting Multimedia Applications," (1996), IEEE Jour. Sel. Area. Comm., Vol. 14, No. 17, pp. 1228-1234, and R. Guerin et al., "QoS Routing Mechanism and OSPF Extensions," Internet Draft, Mar. 25, 1997, demonstrated that concave metrics can be easily handled by simply ignoring those links between nodes that do not satisfy the constraints since a decision can be made locally at a link. For example, all links that do not satisfy the bandwidth constraints can be removed before selecting a route.
Selecting a route is not simple, however, for additive metrics. This is because a decision cannot be made until the value of the metric for each link on a path has been examined. For example, to determine if a path satisfies a given delay constraint it is necessary to compare the sum of the delays of all links on the path to the constraint. Finding an algorithm that can handle two or more additive parameters has been challenging. No efficient, that is to say "polynomial-time", algorithms have been found so far to solve the problem completely, even if not considering any other QoS metrics. Worst of all, it is unlikely that any polynomial-time algorithm can ever be found. The intrinsic difficulty lies in that this problem is in the category of NP-HARD problems. An NP-HARD problem is defined as a problem with n variables for which the computation time is higher than a.sup.n, for some a&gt;1. This problem was identified as NP-HARD in J. M. Jaffe, "Algorithms for Finding Paths with Multiple Constraints," (1984), Networks, Vol. 14, pp. 95-116. For practical purposes, no polynomial time algorithms can be found for any NP-HARD problems.
A few heuristic approaches have been attempted to solve the QoS-oriented route selection problem. A common heuristic algorithm used by several ATM vendors uses Dijkstra's algorithm to find a minimum cost route and check the validity of this route against other constraints. (See, for example, Atshushi Iwata, et al., "PNNI Routing Algorithms for Multimedia ATM Internet," (1997), NEC Res. and Develop., Vol. 38, No. 1; Data Connection, (1997), DC-PNNI Specification.) In the case of failure to find a route, the Dijkstra algorithm is used to find a shortest path route in terms of another additive metric, say delay, and then the validity of this route is checked against other metrics. The problem with this approach is that the algorithm gives up looking for minimum cost routes too easily and is likely to miss existing routes that satisfy all constraints and have minimum cost.
U.S. Pat. No. 5,467,343 issued Nov. 14, of 1995 to Lee proposes to combine all additive metrics into one and then solve the problem in polynomial time. (See also W. C. Lee, et al., "Rule based Call-by-Call Source Routing for Integrated Communication Networks", Infocom '93, pp.987-993, 1993 and W. C. Lee, et al., "Multi-Criteria Routing Subject to Resource and Performance Constraints," ATM Forum, 94-0280, March 1994.) Unfortunately, a function can not generally be formulated for this conversion. This is especially so where the metrics are independent. Consider, for example, delay and cost. At first glance, the delay and cost might be considered related and proportional. However, a carrier may want to consider any route going through a third party's network to be more expensive than his own. Thus, in general, these metrics must be considered to be independent.